package dailyTopic;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2021-08-09 9:44
 *
 * 超级丑数：1.小顶堆   2.动态规划
 */
public class nthSuperUglyNumber313 {
   /* public int nthSuperUglyNumber(int n, int[] primes) {
        //用一个集合来去重
        Set<Long> set=new HashSet<>();
        //用优先队列实现小顶堆
        PriorityQueue<Long> heap=new PriorityQueue<>();
        set.add(1L);
        heap.offer(1L);
        int res=0;
        for (int i = 0; i < n; i++) {
            long now=heap.poll();
            res=(int)now;
            for (int prime:primes) {
                Long temp=now*prime;
                if (set.add(temp))
                    heap.offer(temp);
            }
        }
        return res;
    }*/
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly=new int[n+1];
        //pu用来记录每个primes中元素的乘操作
        int[] pu=new int[primes.length];
        ugly[0]=0;ugly[1]=1;
        Arrays.fill(pu,1);
        for (int i = 2; i <= n; i++) {
            int temp=Integer.MAX_VALUE;
            int[] nums=new int[primes.length];
            for (int j = 0; j < primes.length; j++) {
                nums[j]=ugly[pu[j]]*primes[j];
                temp=Math.min(temp,nums[j]);
            }
            ugly[i]=temp;
            for (int j = 0; j < primes.length; j++) {
                if (ugly[i]==nums[j])
                    pu[j]++;
            }
        }
        return ugly[n];
    }
    public static void main(String[] args) {
        int[] primes=new int[]{2,7,13,19};
        nthSuperUglyNumber313 nthSuperUglyNumber313=new nthSuperUglyNumber313();
        System.out.println(nthSuperUglyNumber313.nthSuperUglyNumber(12,primes));
    }
}
